Location-allocation and public transit

The problem

• UCL IOE (Institute of Education) run a teacher placement programme.
• These students are learning how to become high school teachers and have two 60 day placements at schools.
• They have about 800 students who need to be placed across about 500 schools, across about 5 subject groups.
• Currently they use a combination of Excel spreadsheets and Google Maps (locations and public transport routing) to do this process manually.
• This is very time consuming and would take at least a week per subject group to complete.

We know there is a better way

• Location-Allocation could be a solution to this problem.
  • Find locations for facilities from a set of demand locations.
• Classic example:
  • Where do we put a new hospital so as many residents as possible are within the shortest possible travel time?
  • E.g. ~ run drive-time routes from every house to every possible hospital location. Select the shortest total time.

Initial Results

• Working with James Grindrod - IOE Placement Manager
• Developed an automated way of doing this

What is Location Allocation?

• Has been around in GIS for a long time.

• Very commonly drive-time focused (or walk or cycle….)

• Relatively little in terms of public transport.

• In UCL IOE, public transport is key.

  • About 70% of students use public transport to get to their placement schools.

  • In general, ~8% of people use public transport to get to work Census 2021.

What is Location Allocation?

How did we do this?

• I was contacted by UCL IOE (James Grindrod) and UCL ARC (Tim Machin) to see if there was a better way.
• Many ways of doing location-allocation
  • I’m not an expert on the exact ins and outs of this
• Need to integrate public transport data
  • Can create an OD matrix from TfL API
• Need to work with a large number of students (~800) and schools (~500)
• Considered ArcGIS Pro, FLP Spreadsheet Solver, PySpatialOpt,
• Reached out via Twitter

How did we do this? phase 1

• Qunshan Zhao suggested spopt, part of PySAL, Python
• spopt couldn’t do what I wanted, but happy to develop
• Applied for AGILE funding to do this, successful (+ Glasgow):
  • Rongbo Xu added capacitated p-median location-allocation model to spopt
• UCL ISD supported first phase of development:
  • Patrick Roddy created code to calculate routes for student (postcode) to school (postcode) using TfL API

How did we do this? phase 2

UCL ISD developed a tool for IOE placements team to use

1. Upload
2. Input Data
3. Compute Journeys
4. Allocate
5. Review
6. Export

1. Upload

• Upload the data on students (placements) and schools as CSV.
• Student name, home postcode, transport modes, school restrictions, priority information related to caring, etc.
• School, location, priority, etc.

2. Input Data

• Input Data checks data and highlights any missing data.

3. Compute Journeys

• Uses TfL API to calculate all possible public transport journeys from each student to each school
• Returns a big OD matrix of journey time (mins), number of legs, number of modes
• 800 students and 500 schools takes about 26 hours to process.
• This only needs to be done once.
• Currently being optimised.

4. Allocate

• Can adjust allocation, ‘lock’ students and re-run.
• More-or-less in real time.

4. Allocate

• Can adjust allocation, ‘lock’ students and re-run.
• More-or-less in real time.

5. Review

Check for outliers | Iterative process Review -> Allocate -> Review.

6. Export

Export data as CSV file - for human review and/or re-import into software.

Feedback - early stages

• Demo’d to the IOE users - James Grindrod & Placements team.
• A small subset of data worked well.
• Questions over “why did it allocate this student here?”
  • the algorithm isn’t very transparent.
  • complicated by the fact the data was a small subset of real data, and comparison was with the full data set done by hand.
• Try to show in the software why certain allocations were done.
  • Show range of options for each student.
  • Impact of changing one student on other students travel time, + 3.2 min.

Feedback - early stages

It is intended that there will always be a element of manual allocation needed.

Most restrictions are included in the software, but a few are not present. Some are only stored in the heads of the placements team!

Reflection

• I worked as a bit of a project manager in the early stages

Next Steps

More feedback from IOE - compare a full data set done “by software” and done “by hand” to compare the differences.

Hope to share a Juypter Python Notebook demonstrating the potential of this technique, with dummy data. Levi will do this when he has some time!

Ultimately software to be shared with other users at UCL - e.g. health placements, etc.

And possibly also shared with others.

Open source - not sure? TBC.

Extra Slides

Data Flow